《剑指offer》 17.打印从1到最大的n位数

剑指offer
留言

note: 有点搞不懂这道题是为了考什么，快速幂？《剑指》上面讲的是大数问题，就把大数问题的写法也学习了一下记录下来。

题目描述

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

1
2
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数

方法一 普通暴力

思路

用10的n次幂，来循环得到值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<int> printNumbers(int n) {
        vector<int> ans;
        int max_num = pow(10,n)-1;
        for(int i=1;i<=max_num;i++){
            ans.push_back(i);
        }

        return ans;
    }
};

复杂度分析

  • 时间复杂度$O(10^n)$。显然需要遍历$10^n$个数
  • 空间复杂度$O(1)$。不用什么额外空间

方法二 快速幂

思路

快速幂的思路，前面已经讲了几遍了，公式是

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    int quickPow(int x,int n){
        int res=1;
        while(n){
            if(n&1) res = res*x;
            x *= x;
            n = n >> 1;
        }
        return res;
    }
public:
    vector<int> printNumbers(int n) {
        vector<int> ans;
        int max_num = quickPow(10,n)-1;
        for(int i=1;i<=max_num;i++){
            ans.push_back(i);
        }

        return ans;
    }
};

复杂度分析

  • 时间复杂度$O(10^n)$。显然需要遍历$10^n$个数
  • 空间复杂度$O(1)$。不用什么额外空间

方法三 大数情景

思路

假如返回值不为int数组，则有可能存在大数问题。大数问题一般只能用string类型来存储，因为无论int、long long都有可能无法满足大数的需求。

string字符串做不到+1自动进位，就需要我们进行手动判断。这无疑是非常耗时的，尤其是形如99999这样的数字+1需要判断的位数非常之多。所以换个角度，要求从1到最大n位数的所有数，其实本质上也就是求n位0~9的一个全排列问题，再将全排列可能出现的，前置0的情况去掉0，就得到了我们要的结果。

全排列我们可以利用分治算法的思想进行解决，先固定高位，再递归解决低位，一直到个位固定后，我们就可以将生成的大数进行“去除前置0”的判断和操作，并放入数组或者放入存放答案的字符串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    string s;
    vector<int> ans;
    //string ans;
public:
    vector<int> printNumbers(int n) {
        s.resize(n,'0');
        dfs(n,0);
        //return ans.substr(0,ans.length()-1);
        return ans;
    }

    void dfs(int n,int index){
        if(index==n){
            save();
            return;
        }
        for(int i=0;i<=9;i++){
            s[index] = i+'0';
            dfs(n,index+1);
        }
    }

    void save(){
        int start = 0;
        while(start<s.size()&&s[start]=='0' )    start++;
        if(start!=s.size()){					// 可以帮助我们去除0
            //ans = ans + s.substr() + ",";
            ans.emplace_back(stoi(s.substr(start)));
        }
    }
};

*注释的内容为返回值为string类型时的写法。

复杂度分析

  • 时间复杂度$O(10^n)$。因为排列数量有 $10^n$
  • 空间复杂度$O(n)$。返回数组的空间不算的话，额外空间就是字符串string。